package com.explorati.LeetCode077.combine;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @ Author : Weijian_Wang
 * @ Date : Created in 20:43 2020/9/26 0026
 * @ Description ：
 */
public class Solution {

    /**
     * 给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
     * 输入: n = 4, k = 2
     * 输出:
     * [
     *   [2,4],
     *   [3,4],
     *   [2,3],
     *   [1,2],
     *   [1,3],
     *   [1,4],
     * ]
     * @param n
     * @param k
     * @return
     */
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> combine(int n, int k) {
        if(n <= 0 || k <= 0 || n < k) {
            return res;
        }
        findCombine(n, k, 1, new ArrayList<>());
        return res;
    }

    private void findCombine(int n, int k, int start, List<Integer> preList){
        if(preList.size() == k) {
//            List<Integer> list = new ArrayList<>(preList.size());
//            for(Integer i : preList) {
//                Collections.addAll(list, i);
//            }
            res.add(new ArrayList<>(preList));
            return;
        }

        for(int i = start; i <= n; i ++) {
            preList.add(i);
            findCombine(n, k, i + 1, preList);
            preList.remove(preList.size() - 1);
        }
    }

}
